package leetcode;

/**
 * ClassName: DataStructureOfList
 * Package: leetcode
 * Description:
 *
 * @Author wjn
 * @Create 2025/5/27 21:14
 * @Version 1.0
 */
public class DataStructureOfList {

    /**
     * 移除链表元素（changgui）
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 移除链表元素(虚拟头结点)
     * 好处：统一了头结点处理方式
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements1(ListNode head, int val) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null && head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            // 创建临时变量暂存cur.next
            ListNode temp = cur.next;
            //  将cur.next指向pre
            cur.next = pre;
            //  pre和cur都后移,顺序不要乱
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 两两交换链表中的节点
     * 使用虚拟头结点的方式
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        // 建立虚拟头结点
        ListNode dummyHead = new ListNode();
        //  将虚拟头结点指向head
        dummyHead.next = head;
        // 遍历链表
        ListNode cur = dummyHead;
        // 终止条件为链表为空或者链表只有一个节点
        while (cur.next != null && cur.next.next != null) {
            // 创建临时变量暂存cur.next(节点1)
            ListNode temp = cur.next;
            //(节点三保存)
            ListNode temp1 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp;
            temp.next = temp1;
            //移动cur指针
            cur = cur.next.next;
        }
        return dummyHead.next;
    }

    /**
     * <p>
     * 移除链表中倒数第n个节点
     * </p>
     * 该方法通过双指针技术有效地从链表中移除倒数第n个节点，无需事先知道链表的长度
     * 这是一个常见且具有挑战性的链表操作问题，考验对链表操作的理解和应用能力
     *
     * @param head 链表的头节点，这是链表的起点
     * @param n    要移除的节点的倒数位置，例如，n=1将移除最后一个节点
     * @return 返回修改后的链表的头节点，如果原头节点被移除，则返回新的头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummyHead = new ListNode();
        // 创建虚拟头结点，方便处理头结点的删除情况
        dummyHead.next = head;
        // 快指针先走 n 步，这样当快指针到达链表末尾时，慢指针恰好指向倒数第 n 个节点
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return dummyHead.next;
    }


    /**
     * <p>
     * 链表中环的检测
     * </p>
     *
     * @param head 链表的头节点，这是链表的起点
     * @return 返回链表中环的入口节点，如果没有环，则返回 null
     */
    public ListNode detectCycle(ListNode head) {
        // 使用快慢指针，如果链表中存在环，则快指针和慢指针一定会相遇
        ListNode fast = head;
        ListNode slow = head;
        // 循环条件为链表不为空且链表有下一个节点
        while (fast != null && fast.next != null) {
            // 快指针每次走两步，慢指针每次走一步
            fast  = fast.next.next;
            slow = slow.next;
            //  如果快慢指针相遇，则说明链表中存在环
            if (fast == slow) {
                // 快慢指针相遇后，定义index1为相遇点
                ListNode index1 = fast;
                //  定义index2为链表的起点
                ListNode index2 = head;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    /**
     * <p>
     * 链表相交
     * </p>
     *
     * @param headA 链表A的头节点，这是链表A的起点
     * @param headB 链表B的头节点，这是链表B的起点
     * @return 返回链表相交的起始节点，如果没有相交，则返回 null
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        //求出链表A的长度
        while (curA != null) {
            curA = curA.next;
            lenA++;
        }
        //求出链表B的长度
        while (curB != null) {
            curB = curB.next;
            lenB++;
        }
        // 让curA和curB指向两个链表的头节点
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求出长度差
        int diff = lenA - lenB;
        while (diff > 0) {
            curA = curA.next;
            diff--;
        }
        //  两个链表同时开始遍历
        while (curA != null && curB != null) {
            //  如果两个节点相同，则返回该节点
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

}
